package leetcode.code0497;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int[][] rects;
	long max = 0;
	long[][] ranges;
	int len;
	public Solution(int[][] rects) {
		this.rects = rects;
		len = rects.length;
		ranges = new long[len][2];
		// 矩形擀平
		for (int i = 0; i < len; i++) {
			int[] cur = rects[i];
			int a = cur[0], b = cur[1], x = cur[2], y = cur[3];
			ranges[i][0] = max;
			max += (x - a + 1) * (y - b + 1);
			ranges[i][1] = max - 1;
		}
	}

	public int[] pick() {
		// 随机一个数值
		int random = (int) (Math.random() * max);
		// 找到这个值是第几个矩形的第几个点
		int l = 0, r = len - 1;
		int index = 0;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			if (ranges[mid][0] <= random && random <= ranges[mid][1]) {
				index = mid;
				break;
			} else if (random < ranges[mid][0]) {
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		long no = random - ranges[index][0];
//		int m = rects[index][3] - rects[index][1];
		int n = rects[index][2] - rects[index][0] + 1;// +1
		long ansy = rects[index][3] - no / n , ansx = no % n + rects[index][0];
		return new int[] { (int) ansx, (int) ansy };
	}

	private int random(int range, int start, int end, int ans) {
		for (int i = start; i <= end; i++) {
			int random = (int) (Math.random() * (++range));
			if (random == 0) {
				ans = i;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution(H.str2array1("[[-2,-2,1,1],[2,2,4,6]]"));
		so.pick(); // 返回 [1, -2]
//		so.pick(); // 返回 [1, -1]
//		so.pick(); // 返回 [-1, -2]
//		so.pick(); // 返回 [-2, -2]
//		so.pick(); // 返回 [0, 0]
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

}
